package leetcode.pre50;

import java.util.LinkedList;
import java.util.List;

/**
 * 给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
 * <p>
 * 例如，给出 n = 3，生成结果为：
 * <p>
 * [
 * "((()))",
 * "(()())",
 * "(())()",
 * "()(())",
 * "()()()"
 * ]
 * <p>
 * 其他括号问题见
 * {@link leetcode.a_总结分布.Code03_括号问题}
 * @date 2020/3/24 14:41
 */
public class Code22_产生括号 {
    //方式1：暴力回溯。每个位置都产生(或)。最后剪枝。O(2^(2n))
    //判断单种括号是否合法
    private static boolean legal(String s) {
        if (s == null || s.length() == 0) return true;
        //方式1：可以使用栈。
        //方式2：只要保证当前左括号数大于等于右括号数，则可以继续下去
        //但是右括号大于左括号，肯定不合法
        int balance = 0;
        for (int i = 0; i < s.length(); i++) {
            if (balance < 0) return false;
            if (s.charAt(i) == '(') {
                balance++;
            } else {
                balance--;
            }
        }
        return balance == 0;
    }

    //方式2：提前剪枝。仍然存在的问题是，左括号可能已经超了n，结果肯定会被舍弃
    public static List<String> generateParenthesis(int n) {
        List<String> res = new LinkedList<>();
        if (n <= 0) return res;
        process(res, 0, 0, n, "");
        return res;

    }

    private static void process(List<String> res, int balance, int index, int n, String curRes) {
        if (balance < 0) return;
        //左括号可能已经超了n，结果肯定会被舍弃。可以提前剪枝
        if (balance > n) {
            return;
        }
        //从0-2n-1
        if (index == 2 * n) {
            if (balance != 0) return;
            res.add(curRes);
            return;
        }
        //当前位置产生左括号或右括号
        process(res, balance + 1, index + 1, n, curRes + "(");
        process(res, balance - 1, index + 1, n, curRes + ")");
    }

    /**
     * 方式3：动态规划。
     * 假设有i对括号已经生成，那么i+1对括号是怎么生成的？
     * i+1对括号的结果是，对0-i对括号分别套括号。
     * ( s1 ) s2。
     * 其中s1从0对括号遍历到i对。
     * s2也是从0对括号遍历到i对。
     * 切二者括号对数满足p+q = i。
     * 这是所有正确的结果。
     */
    public static List<String> generateParenthesis3(int n) {
        if (n <= 0) return new LinkedList<>();
        //dp.get(n)表示n对括号结果。dp存储了0-n对括号所有结果
        List<List<String>> dp = new LinkedList<>();
        //产生0对括号的结果
        List<String> dp0 = new LinkedList<>();
        dp0.add("");
        dp.add(dp0);
        //括号总对数
        for (int i = 1; i <= n; i++) {
            //对于第i对括号，考虑前i-1对括号可能的组成。
            //一直从0对到 i-1对。
            //存储 n = i时，所有括号的结果
            List<String> cur = new LinkedList<>();
            for (int j = 0; j < i; j++) {
                //二者之和是 i - 1
                List<String> str1 = dp.get(j);
                List<String> str2 = dp.get(i - 1 - j);
                //遍历，镶嵌
                for (String s1 : str1) {
                    for (String s2 : str2) {
                        cur.add("(" + s1 + ")" + s2);
                    }
                }
            }
            dp.add(cur);
        }
        return dp.get(n);
    }


}
